Electronic memories suffer several types of faults when data is written to them. Testing for these faults is very difficult, and particularly poses a problem when it is desired to build testing capability into the electronic memory itself.
A very general fault type that can model most of the reported erroneous interactions involving V.gtoreq.2 arbitrary RAM storage cells is the single V-coupling fault defined by Nair, Thatte, and Abraham ("Efficient Algorithms for Testing Semiconductor Random-Access Memories," IEEE Trans. on Comp., v. C-27, no. 6, pp. 572-576, June 1978). Nair, Thatte, and Abraham defined the single V-coupling fault to represent the situation when V.gtoreq.2 cells, say cells i.sub.1, . . . ,i.sub.v, interact erroneously as follows: if cells i.sub.1, . . . ,i.sub.v contain V particular values b.sub.1, . . . ,b.sub.v and if cell i.sub.1 is written to -b.sub.1, then the contents of both cells i.sub.1 and i.sub.2 are changed. A particular case, the 5-coupling fault, can be used to model active neighborhood pattern-sensitive faults (ANPSFs) as defined by Suk and Reddy ("Test Procedures for a Class of Pattern-Sensitive Faults in Semiconductor Random-Access Memories," IEEE Trans. on Comp., v. C-29, no. 6, pp. 419-429, June 1980); this follows because every ANPSF is also a 5-coupling fault. Testing for 5-coupling faults is in fact equivalent to testing for ANPSFs when there is no knowledge of the mapping from logical cell addresses to physical cell locations.
Efficient tests for detecting ANPSFs, such as Suk and Reddy's TANPSF1, presuppose knowledge of the address mapping. However, the mapping is often not readily available due to vendor secrecy and unannounced layout changes. A further complication is that the widespread use of redundant rows and/or columns to repair defective RAMs disturbs the address mapping in different ways for each RAM die. Indeed, in RAMs with multiple sub-arrays, the address mapping is likely to be different in each sub-array. Testing for V-coupling faults avoids the address mapping problem altogether because the fault model is independent of the physical arrangement of the cells.
In addition, RAMs are often embedded in larger integrated circuits (ICs) such as microprocessors and digital communications ICs; this practice can cause problems at test time because access to the RAM inputs and outputs for testing purposes is often difficult or impractical. RAMs provided with built-in self-test (BIST) such as the design proposed by Dekker et al (R. Dekker, F. Beenker, and L. Thijssen, "A Realistic Self-Test Machine for Static Random Access Memories," Proc. 1988 Int. Test Conf., Sept. 12-14, 1988, pp. 353-361, Washington, D.C., U.S.A., (IEEE Comp. Soc.)), tackle this problem by avoiding the necessity of routing test data to and from the RAM through intervening logic. A second RAM testing challenge is that it is often desirable to increase a system's effective reliability by periodically testing its memory while the system is in service. Nicolaidis ("Transparent BIST for RAMs," Proc. 1992 Int. Test. Conf., Baltimore, Md., U.S.A., Sept. 20-24, (IEEE Comp. Soc., Washington,1992), pp. 598-607) tackled this additional problem by developing a method whereby the self-test routine produced by a BIST RAM is made transparent, that is, the contents of the RAM initially present when the self-test was started are restored, if the RAM is fault-free, by the end of the test. RAMs with transparent BIST can thus be tested periodically in a running system, without requiring that the stored data be first copied out and stored elsewhere for the duration of the test, and then rewritten back to the RAM once the test has completed.
Nicolaidis' method requires that a proposed RAM self-test be first transformed in a series of steps. Essentially these steps ensure that the data in each RAM cell is complemented an even number of times during the application of the test. The transformed test is applied in two phases: In the first phase, only read operations are applied to the RAM as a first data-dependent signature is computed. In the second phase, both read and write operations are applied while a second signature is computed. The RAM is deemed fault-free if the two signatures agree. The scheme is vulnerable to the small but finite chance of aliasing, when the two signatures are the same in the presence of a fault. Aliasing is possible even if the original memory test is deterministic, i.e., has 100% fault coverage over the assumed fault universe. However, the probability of aliasing can always be reduced by using longer signatures. When a deterministic test is used to construct a transparent test, we call the resulting test near-deterministic. By a probabilistic test we will mean either a nontransparent test that has less than 100% fault coverage, or a transparent test based on such a nontransparent test.